package com.le.tester.imooc.oldfairy.coding.datastructure;

import com.le.tester.javaThink.fourth.net.mindview.util.DaemonThreadFactory;
import org.junit.Test;

import java.util.HashSet;
import java.util.Set;
import java.util.function.Predicate;

import static org.junit.Assert.assertEquals;

/**
 * createTime：2023/5/25 14:49
 * description：List single linked
 */
public class LList<T> {

    static class Node<T> {
        Node<T> next = null;
        T data;

        public Node(T data) {
            this.data = data;
        }
    }

    Node<T> head = null;


    //头部插入
    public void insert(T data) {

        Node node = new Node<>(data);
        //指针指向下一个连接链表，此时node还不是头
        node.next = head;
        //把Node置于头位
        head = node;
    }

    //使用jpa自带的查询条件方式
    public Node<T> find(Predicate<T> predicate) {
        Node<T> head = this.head;
        while (head != null) {
            if (predicate.test(head.data)) {
                return head;
            }
            head = head.next;
        }
        return null;
    }

    //移除
    public void remove(Node<T> node) {
        if (null == head) {
            return;
        }

        if (head == node) {
            head = head.next;
            return;
        }

        Node<T> slow = this.head;
        Node<T> fast = head.next;
        while (slow != fast && fast != null) {
            //理解为位置的移动吧,并不破坏最初链表的结构
            slow = fast;
            fast = fast.next;

        }

//        if (fast != null) {
//            slow.next = fast.next;
//        }
    }

    @Test
    public void test_insert() {
        LList<Integer> list = new LList<>();
        list.insert(1);
        list.insert(2);
        list.insert(3);

        Node<Integer> head = list.head;

        for (Integer i = 3; head != null; i--) {

            assertEquals(i, head.data);
            head = head.next;
        }

    }


    //循环反转链表
    public void reverse() {
        Node<T> prev = null;
        Node<T> curr = head;
        Node<T> next;

        while (curr != null) {
            next = curr.next;
            //直接把head的下一个位置移动到之前
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
    }

    public Node<T> _reverse2(Node<T> head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node<T> rest = _reverse2(head.next);
        head.next.next = head;
        head.next = null;
        return rest;
    }

    public void reverse2() {
        head = _reverse2(head);
    }

    //双向链表中是否有环
    public boolean hasLoop1() {
        Set<LList.Node<T>> set = new HashSet<>();

        Node<T> p = this.head;
        while (p != null) {
            if (set.contains(p)) {
                return true;
            }
            set.add(p);
            p = p.next;
        }
        return false;
    }


    public boolean hasLoop2() {
        if (head == null || head.next == null) {
            return false;
        }

        Node<T> slow = this.head;

        Node<T> fast = head.next.next;

        while (fast != null && fast.next != null) {
            if (slow == fast) {
                return true;
            }

            slow = slow.next;
            fast = fast.next.next;

        }
        return false;
    }

}
